//Floyd求任意两点的最短路径【动态规划】【能处理带负权的图，不能处理带负权回路的图；时间复杂度为O(|V|^3)】
/*
    状态转移方程：若A(k-1)[i][j] > A(k-1)[i][k] + A(k-1)[k][j]
                则 A(k)[i][j] = A(k-1)[i][k] + A(k-1)[k][j];
                path(k)[i][j] = k.
                否则A(k)和path(k)不变。
*/

/*
    使用动态规划的思想，将问题的求解分为多个阶段

    对于n个顶点的图G，求任意一堆顶点 Vi -> Vj 之间的最短路径课分为以下几个阶段
    #初始：不允许在其他顶点中转，最短路径是？
    #0：若允许在V0中转，最短路径是？
    #1：若允许在V0、V1中转，最短路径是？
    #2：若允许在V0、V1、V2中转，最短路径是？
    ……
    #n-1:若允许在V0、V1、V2 …… Vn-1中转，最短路径是？
    即分为n个阶段，最开始不允许中转，然后每下一个阶段，就加入一个可以中转的结点，直到最后n(V0 …… Vn-1)个结点都可以中转。
*/

#include "MGraph.h"
#include <iostream>
#include <memory.h>

using namespace std;

void OutPath(int path[][100], int x, int y) //递归输出两点间的最短路径
{
    if (path[x][y] == -1)
    {
        cout << "(" << x << "," << y << ")";
        return;
    }
    OutPath(path, x, path[x][y]);
    OutPath(path, path[x][y], y);
}

int main()
{
    MGraph G;           //以邻接矩阵存储的图
    cout << "1:Directed graph  ||  0:Undirected graph\nchoose 1 or 0: ";
    cin >> G.DirStatue; //1:有向图 || 0:无向图
    cout << "input vertex and arc:\n";
    cin >> G.vexnum >> G.arcnum;  //确认该图顶点数和边数
    Init(G);            //初始化图G

    //得到该图的邻接矩阵
    cout << "please input (x y weight):\n";
    for (int x, y, weight, i = 0; i < G.arcnum; ++i)
    {
        cin >> x >> y >> weight;
        AddEdge(G, x, y, weight);
    }

    EdgeType A[MaxVertexNum][MaxVertexNum]; //二维数组A用于进行Floyd算法变化
    memcpy(A, G.Edge, sizeof(G.Edge));      //初始化数组A为图的邻接矩阵
    int path[MaxVertexNum][MaxVertexNum];   //二维数组path用于计算两点走最短路径的距离(可用递归的思想得到最短路径)
    memset(path, -1, sizeof(path));         //初始化数组path为-1  (sizeof(path); <=> sizeof(int)*100*100;)



    //Floyd算法
    for (int k = 0; k < G.vexnum; ++k)              //考虑以Vk作为中转点
    {
        for (int i = 0; i < G.vexnum; ++i)          //遍历整个矩阵，i为行号，j为列号
        {
            for (int j = 0; j < G.vexnum; ++j)
            {
                if (A[i][j] > A[i][k] + A[k][j])    //【注意：这里是核心】若发现从Vi到Vj以Vk为中转点的路径更短
                {
                    A[i][j] = A[i][k] + A[k][j];    //更新最短路径长度
                    path[i][j] = k;                 //把中转点记入path数组
                }
            }
        }
    }


    //测试代码
    int x, y;
    cin >> x >> y;
    printf("The Shortest Path from %d to %d is: %d\n", x, y, A[x][y]);
    cout << "And the path is:";
    OutPath(path, x, y);
    return 0;
}